# -*- coding: utf-8 -*-            
# @Time : 2022/10/30 14:29
# @Author  : lining
# @FileName: demo7.py
"""
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
中缀表达式求值
（1）不带（）的表达式，先转成后缀表达式去计算。
[1]*/优先计算，+-后计算
s = " 2 - 1 + 2 * 2"   2 1 -2 2 * +
s = " 2 - 1 + 2 * 2 * 2 - 1"   2 1 -2 2 *2* +1-
2,-入栈，1入栈，遇到+和栈顶比较，是同级，先把-出栈，变成2，1，-，把+入栈，2入栈，遇到*和栈顶比较优先级比较高，先入栈，
然后把栈顶弹出，把+弹出
遇到数字，放到字符串后面，遇到运算符，先和栈顶运算符比较，如果是同级，先出栈顶运算，然后把当前运算符入栈，如果更高级
"""
class Solution(object):
    def evalRPN(self, tokens):
        """
        :param tokens: 字符串类型，用空格分割
        :return:
        """
        # 存放运算符的栈
        stack_op = []
        # 存放后缀表达式
        stack_express = []
        token = tokens.strip().split(' ')
        for i in token:
            # 如果是数字就入栈
            if i.isdigit():
                stack_express.append(i)
                continue
            # # 运算符空的时候直接入栈
            # if len(stack_op) == 0:
            #     stack_op.append(i)
            #     continue
            # # 运算符先和栈顶比较优先级
            # # 当前运算符优先级大于栈顶运算符
            # if self.compare_operate(i) > self.compare_operate(stack_op[-1]):
            #     # 入栈
            #     stack_op.append(i)
            #     continue
            # 当前运算符优先级小于栈顶运算符，弹出栈顶，加入表达式栈，然后将当前运算符入栈,
            # 一直比较直到栈顶小于当前运算符
            while stack_op and (self.compare_operate(i) <= self.compare_operate(stack_op[-1])):
                    op = stack_op.pop()
                    stack_express.append(op)
            stack_op.append(i)
        # 遍历完字符串，操作符栈还有内容把操作符都添加到字符串后面
        if len(stack_op) > 0:
            stack_op.reverse()
            stack_express.extend(stack_op)
        print(' '.join(stack_express))

    def compare_operate(self, op):
        """
        比较操作符优先级
        :return:
        """
        if op in ['+', '-']:
            return 1
        return 2


s = " 1 + 2 + 3 + 4 * 5"
Solution().evalRPN(s)
